\documentclass[a4paper,12pt]{scrreprt} 
\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage[ngerman]{babel}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{textcomp}
\usepackage{makeidx}
\usepackage{multicol}
\usepackage{graphicx}
\usepackage{longtable}
\usepackage{tabularx}
\usepackage{hyperref}
\usepackage{pst-all}
\usepackage{listings}

\makeatletter
\newcommand*{\heading}[1]{
  \makebox[0pt][l]{
    \rule[-3pt]{\linewidth}{0.5pt}}
  \textsf{\textbf{\Large #1}}\hfil\nopagebreak\vspace{4pt}}

\renewenvironment{theindex}{
  \setlength{\columnseprule}{0.4pt}
  \setlength{\columnsep}{2em}
  \begin{multicols}{2}[\chapter*{\indexname}]
   \parindent\z@
   \parskip\z@ \@plus .3\p@\relax
   \let\item\@idxitem}
  {\end{multicols}\clearpage}
\makeatother

\title{SO-Compiler \\ The official documentation}
\author{Sebastian Hahn\\ saarinformatix@googlemail.com\\ Deutschland}
\date{Sulzbach, den \today}
\makeindex

\begin{document}
\pagenumbering{Alph}
\maketitle
%\frontmatter
\pagenumbering{roman}
\section*{Vorwort}
Es freut mich, dass Sie den Weg zu dieser Dokumentation gefunden haben und Sie sich für mein Projekt interessieren. \\[0.2cm] Die Frage, die man häufig gestellt bekommt, wenn man sich ein Projekt wie die Entwicklung eines Compilers vornimmt ist: \textgravedbl Warum machst du sowas, es gibt doch so viele Compiler, es ist doch unwahrscheinlich, dass sich deine Idee durchsetzt.\textacutedbl\  Nun möchte ich es ein für alle mal festhalten. Ich bin nicht daran interessiert neue Industriestandards durchzusetzen. Dieses Projekt dient lediglich zum Erlernen von Techniken des Compilerbaus. Außerdem lernen die Projektteilnehmer etwas darüber, wie man eine objektorientierte Sprache realisieren kann. Dieses Projekt ist also \textbf{nicht} zum \textbf{Produktiveinsatz} geeignet, sondern nur zum Lernen geeignet.\\[0.2cm]
Diese Dokumentation soll dabei helfen den Aufbau dieses Compilers im Groben zu verstehen. Für die Programmierer dient diese Dokumentation als Referenzhandbuch.\\[0.2cm]
Viel Spaß noch und schauen Sie auch auf der \href{http://sobjects.funpic.de}{SObjects - Homepage} vorbei.\newline
Sebastian Hahn
\section*{Danksagung}
Ich möchte mich bei allen bedanken, die zum Gelingen dieser Dokumentation durch Korrekturlesen, etc. und/oder zum Gelingen des Projektes durch Teilnahme an Diskussionen im \href{http://sobjects.funpic.de/forum/phpBB3/}{Forum} durch Mitprogrammieren oder durch das Melden von Bugs beigetragen haben. Sollten Sie einen Fehler in dieser Dokumentation finden, können Sie mir eine E-Mail an \href{mailto:sebastianhahn@gmx.de}{sebastianhahn@gmx.de} senden.
\tableofcontents
%\mainmatter
\newtheorem{Def}{Definition}
\part{SO - Compiler}
\pagenumbering{arabic}
\chapter{Einleitung}
\section{Motivation}
Ich finde, am Anfang eines Buches sollte immer eine Art Motivation stehen, um den Lesern aufzuzeigen, wozu man ein Buch überhaupt schreibt.\\[0.2cm] Also ich, Informatikstudent der Universität des Saarlandes in Saarbrücken, habe mir im Laufe der Zeit in den Kopf gesetzt einen Compiler zu programmieren. Nicht, wie im Vorwort bereits gesagt, um neue Standards zu setzen, sondern lediglich um zu lernen wie ein Compiler intern funktioniert, da es mich seither faszinierte, komplexe Programme auf Maschinenniveau zu übersetzen. Also habe ich im August 2008 zusammen mit einem Komilitonen angefangen Ideen zu sammeln.\\[0.2cm] Compiler sind wohl einer der \textit{zentralsten} und \textit{wichtigsten} Themen der Informatik. In diesem Buch werde ich versuchen, den Aufbau meines Compilers ansatzhaft zu erläutern. Viel Spaß.
\section{Grober Plan}
Die Hauptidee war es, eine Java\footnote{Java-URL: \url{http://java.sun.com/}}-artige Programmiersprache zu entwickeln, 
die aber, von vielen als \textgravedbl fehlend\textacutedbl\ bezeichnete Elemente wie überladenen Operatoren enthalten 
soll. Also stellte sich die zentrale Frage für welche Plattform Zielcode erzeugt werden soll. Eine eigene VM (virtual 
machine) ? Oder eine bereits existierende VM nutzen ? Oder gar direkt maschinenabhängigen Assemblercode erzeugen ? 
Durch einen Tipp wurde ich auf eine gerade zu perfekt geeignete \textgravedbl Schnittstelle\textacutedbl\ aufmerksam: 
LLVM\footnote{LLVM-URL: \url{http://llvm.org/}}\index{LLVM} (low level virtual machine). Das Lesen der LLVM Language 
Reference Manual\footnote{\url{http://llvm.org/docs/LangRef.html}} machte mir schnell klar: An eine solche VM kommt 
eine eigen programmierte nicht heran.\\[0.2cm] Somit war es entschieden. Das Projekt SO-Framework wurde reduziert. 
Die sehr provisorische und schwache SO-VM wurde aus dem SVN-Repository gelöscht. Der Compiler war ab sofort rein auf 
LLVM-Bytecode-Erzeugung ausgelegt. Übrigens: Der Compiler wird in der Programmiersprache Java geschrieben.
\section{Stand zu Beginn des Buches (14.12.2008)}
Ja, heute \dots\ Der Compiler steht als Prototyp für SO-VM als Download bereit. Der Support dafür ist bereits eingestellt. Der SO-Compiler wird von Grund auf neu programmiert. Alte Programmteile überwiegen im Moment. Lediglich der Lexer ist fertig. Die Arbeit stockte beim Parser. Also noch viel Arbeit. Zeit für die Erstellung eines konkreteren Plans.
\section{Kurzfristiger Plan}
Die kurzfristige Zielsetzung zielt auf die Implementierung der folgenden Basis-Features ab:
\begin{itemize}
 \item Unterstüzung von Klassen
 \item Erzeugung von Objekten
 \item Konstruktoren und Methoden
 \item Grundrechenarten und Basisoperatoren
 \item Schleifen
 \item If-Anweisungen
 \item Arrays
 \item Post- und Pre- Inkrement- und Dekrementanweisungen
 \item Vererbung mit dynamischen und statischen Typen
 \item Unterstützung von Import-Anweisungen
\end{itemize}
\section{Langfristiger Plan}
Langfristig gesehen sollen folgende Erweiterungen kommen:
\begin{itemize}
 \item Unterstützung von Interfaces
 \item Unterstützung von Enumerations
 \item Unterstützung von Templates
 \item Weitere Schleifen
 \item Switch-Anweisungen
 \item Einige überladbare Operatoren
\end{itemize}
\chapter{Paketstruktur}
Hier möchte ich die Grobstruktur des Compiler aufzeigen.
\begin{center}
 \includegraphics[width=10cm]{struktur.eps}
\end{center}
\begin{itemize}
 \item[code:] Dieses Paket soll alle nötigen Klassen und Methoden bereitstellen, die für die LLVM-Bytecode-Generierung 
nötig sind.
 \item[compiler:] Das Paket \textit{compiler} ist das Haupt-Paket und verwaltet die Interaktion der einzelnen Compiler 
Komponenten. Zuerst wird der Quellcode an den Lexer übergeben, das Result an den Parser, der wiederum ein Objekt vom Typ \textit{Tree} zurückgibt. Auf diesem Objekt werden nun die jeweiligen Analyse-Phasen ausgeführt. Dieses Paket wickelt die Eingabe des Quellcodes, sowie die Ausgabe des Bytecodes ab. Des Weiteren kann die Interaktion innerhalb des Compilers durch Kommandozeilenparameter beeinflusst werden.
 \item[lexer:] Dieses Paket stellt eine Klasse für Tokens bereit, sowie die eigentliche Lexer-Klasse, auf deren Aufgabe 
ich später eingehen werde.
 \item[parser:] Das Paket \textit{parser} stellt die Klasse Parser bereit, sowie eigens angepasste Exceptions.
 \item[tree:] Dieses Paket stellt neben den Interfaces TreeFactory und Tree, sowie den schablonenhaften 
Implementierungen, eine Schnittstelle für die Namensbereiche bereit.
 \item[special\_tree:] Diess Paket stellt angepasste Implementierungen für die unterschiedlichen Äste des 
\textit{Abstract Syntax Tree} bereit, die vor allem die jeweiligen Analyse-Phasen spezialisieren.
 \item[tests:] Das Paket \textit{tests} stellt neben den Schnittstellen für die Testprogrammierung auch konkrete Tests 
für die jeweiligen Stufen des Compilers bereit.
\end{itemize}
Im Nachfolgenden gehe ich jetzt genauer auf die einzelnen Bestandteile eines Compilers ein, sowie deren Umsetzung. 
Auch werde ich die Funktionsweise der einzelnen Klassen oberflächlich darstellen. Genaueres entnehmen Sie bitte dem 
Java-Doc auf der Website.
\chapter{Lexer}
\index{Lexer}
\section{Funktion eines Lexers}
\index{Lexer!Definition}
Lexer ist ein Kurzwort für \textit{lexikalischer Scanner}. Dabei handelt es sich um ein Computerprogramm oder eine 
Routine zur Zerlegung von Eingaben, hier dem Quelltext, in Folgen von logisch zusammengehörigen Einheiten, so genannte 
Tokens.
\section{Schnittstellen des SO-Lexers}
Ursprünglich war als einzige Schnittstelle des Lexers Java's Interface \textit{Iterator<Object>} gedacht. Doch an 
einigen Stellen im Parser fiel auf, dass das sogenannte \textit{Pattern Matching} besser funktioniert wenn man die 
Möglichkeit hat, im Token-Strom einige Stellen zurück springen zu können. Da dies mit \textit{Iterator} nicht möglich 
ist, wird mit einer Getter-Methode die zweite Schnittstelle implementiert. Die Methode gibt ein Array, das den Token 
Stream enthält, an den Aufrufer zurück. Für nähere Informationen bitte die \href{http://sobjects.funpic.de/doc}{Java-Doc} konsultieren.
\section{Token}
\index{Token}
\begin{Def}
 Ein \textbf{Token} ist eine kleinste lexikalische Einheit. Ein Token repräsentiert in der Regel ein Schlüsselwort, einen
Bezeichner, Operatoren, andere Sonderzeichen, sowie Bezeichner und Konstanten. Ein Token beinhaltete neben dem Typ des
Token und der Zeilen- und Spaltenangabe auch optional ein Textfeld, in dem sowohl der Name eines Bezeichners als auch die
Darstellung einer Konstante (z.B.: 123) gespeichert werden können.
\end{Def}
Eine Liste von solchen Tokens kann das ganze Programm in Textform repräsentieren.
Die konkrete Implementierung der Klasse Token ist im Java-Doc ausreichend erklärt.
\pagebreak
\section{TokenTypes und ihre Bedeutung}
Hier werde ich nun alle Token-Typen auflisten und ihre jeweilige Bedeutung kurz erläutern.
\footnotesize
\begin{longtable}{p{3.6cm}p{8.6cm}p{2.2cm}}
\textbf{Token-Typ}&\textbf{Bedeutung}&\textbf{Stringre-präsentation}\\
 \multicolumn{3}{c}{\textbf{Artificial Tokens}} \\
 ERR & Dies ist ein künstlicher Token-Typ und wird immer in den Token-Strom aufgenommen, wenn ein nicht lexbares Zeichen auftaucht. & \\
EOF & Dies ist ebenfalls ein künstlicher Token-Typ und wird an das Ende eines jeden Token-Stroms angehängt, um dem Parser das Ende des Token-Stroms aufzuzeigen. & \\
LIST & Auch dies ist ein \textit{artificial} Token-Typ und wird nur bei Tokens von ListTree und BlockTree (\textit{special\_tree}) genutzt. & \\
\\
\multicolumn{3}{c}{\textbf{Separators}} \\
LBRACE & Token-Typ für \{ - Zeichen & \{ \\
RBARCE & Token-Typ für \} - Zeichen & \} \\
LPAREN & Token-Typ für ( - Zeichen & ( \\
RPAREN & Token-Typ für ) - Zeichen & ) \\
LSQBRAC & Token-Typ für [ - Zeichen & [ \\
RSQBRAC & Token-Typ für ] - Zeichen & ] \\
LARROWBRACKET & Token-Typ für < - Zeichen & < \\
RARROWBRACKET & Token-Typ für > - Zeichen & > \\
SEMI & Token-Typ für Semikolon & ; \\
COMMA & Token-Typ für Komma & , \\
COLON & Token-Typ für Doppelpunkt & : \\
POINT & Token-Typ für Punkt & . \\
\\
\multicolumn{3}{c}{\textbf{Statement-Keywords}} \\
WHILE & Token-Typ für die Einleitung einer While-Schleife & while \\
RETURN & Token-Typ für die Einleitung eines Return-Statements & return \\
FOR & Token-Typ für die Einleitung einer For-Schleife & for \\
SWITCH & Token-Typ für die Einleitung eines Switch-Statements & switch \\
CASE & Token-Typ für die Einleitung eines \textit{case}-Blockes innerhalb eines Switch-Statements & case \\
DEFAULT & Token-Typ für die Einleitung eines \textit{default}-Blockes innerhalb eines Switch-Statements & default \\
IF & Token-Typ für die Einleitung einer If-Verzweigung & if \\
ELSE & Token-Typ für die Einleitung des \textit{else}-Zweiges in einem If-Statement & else \\
\\
\multicolumn{3}{c}{\textbf{Identifier}} \\
IDENT & Token-Typ für die Signalisierung, dass es sich bei dem Token um einen Bezeichner handelt. & \\
\\
\multicolumn{3}{c}{\textbf{Literale}} \\
INT\_LITERAL & Token-Typ für die Signalisierung, dass es sich bei dem vorliegenden Token um eine Ganzzahl handelt. & \\
DOUBLE\_LITERAL & Token-Typ für die Signalisierung, dass es sich bei dem vorliegenden Token um eine Fließkommazahl mit doppelter Genauigkeit handelt. & \\
CHAR\_LITERAL & Token-Typ für die Signalisierung, dass es sich bei dem vorliegenden Token um einen Zeichen (Buchstabe, Ziffer, Escape-Zeichen) handelt. & \\
TRUE\_LITERAL & Token-Typ, der den Wahrheitswert \textit{wahr} repräsentiert. & true \\
FALSE\_LITERAL & Token-Typ, der den Wahrheitswert \textit{falsch} repräsentiert. & false \\
LONG\_LITERAL & Token-Typ, der signalisiert, dass es sich bei dem vorliegenden Token um eine große Ganzzahl handelt. & \\
FLOAT\_LITERAL & Token-Typ, der signalisiert, dass es sich bei dem vorliegenden Token um eine Fließkommazahl mit einfacher Genauigkeit handelt. & \\
NULL\_LITERAL & Token-Typ, der das \textit{null}-Literal repräsentiert. & null \\
STRING\_LITERAL & Token-Typ, der signalisiert, dass es sich bei dem vorliegenden Token um eine Zeichenkette handelt. & \\
\\
\multicolumn{3}{c}{\textbf{Types}} \\
CHAR\_TYPE & Token-Typ, der für den Zeichen-Typ steht & char \\
DOUBLE\_TYPE & Token-Typ, der für den Fließkommazahl-Typ steht & double \\
INT\_TYPE & Token-Typ, der für den Ganzzahl-Typ steht & int \\
LONG\_TYPE & Token-Typ, der für den Ganzzahl-Typ steht & long \\
FLOAT\_TYPE & Token-Typ, der für den Fließkommazahl-Typ steht & float \\
BOOL\_TYPE & Token-Typ, der für den Wahrheitswert-Typ steht & boolean \\
VOID\_TYPE & Token-Typ, der für den \textit{leeren} Typ steht & void \\
STRING\_TYPE & Token-Typ, der für den Zeichenketten-Typ steht & string \\
\\
\multicolumn{3}{c}{\textbf{Assignment-Operatoren}} \\
ASSIGN & Token-Typ, der für die normale Zuweisung steht & = \\
DIVIDEASSIGN & Token-Typ, der folgende Zuweisung repräsentiert \newline $x$ /= $a \Leftrightarrow x = x / a$ & /= \\
MULASSIGN & Token-Typ, der folgende Zuweisung repräsentiert \newline$x$ *= $a \Leftrightarrow x = x * a$ & *= \\
MODULOASSIGN & Token-Typ, der folgende Zuweisung repräsentiert \newline $x$ \%= $a \Leftrightarrow x = x\ \%\ a$ & \%= \\
MINUSASSIGN & Token-Typ, der folgende Zuweisung repräsentiert \newline $x$ -= $a \Leftrightarrow x = x - a$ & -= \\
PLUSASSIGN & Token-Typ, der folgende Zuweisung repräsentiert \newline $x$ += $a \Leftrightarrow x = x + a$ & += \\
SHIFTLEFTASSIGN & Token-Typ, der folgende Zuweisung repräsentiert \newline $x <<= a \Leftrightarrow x = x << a$ & $<<=$ \\
SHIFTRIGHTASSIGN & Token-Typ, der folgende Zuweisung repräsentiert \newline $x >>= a \Leftrightarrow x = x >> a$ & $>>=$ \\
BITANDASSIGN & Token-Typ, der folgende Zuweisung repräsentiert \newline $x\ $\&=$\ a \Leftrightarrow x = x\ \&\ a$ & \&= \\
BITORASSIGN & Token-Typ, der folgende Zuweisung repräsentiert \newline $x\ $|=$\ a \Leftrightarrow x = x\ |\ a$ & |= \\
BITXORASSIGN & Token-Typ, der folgende Zuweisung repräsentiert \newline $x\ ^{\wedge}=\ a \Leftrightarrow x = x ^ a$ & $^{\wedge}=$ \\ \\
\pagebreak
\multicolumn{3}{c}{\textbf{Objektorientierte Elemente}} \\
NEW & Token-Typ, der die Instanzierung eines Objektes einleitet & new \\
CLASS & Token-Typ, der die Definition einer Klasse einleitet & class \\
INTERFACE & Token-Typ, der die Definition eines Interfaces einleitet & interface \\
ENUM & Token-Typ, der die Definition eines Enumerationstyps einleitet & enum \\
TEMPLATE & Token-Typ, der die Definition eines Templates einleitet & template \\
MAINCLASS & Token-Typ, der die Festlegung der Main-Klasse einleitet & MainClass \\
EXTENDS & Token-Typ, der die Vererbung einer Klasse einleitet & extends \\
IMPLEMENTS & Token-Typ, der die Vererbung einer Klasse von einem Interface einleitet & implements \\
CONSTRUCT & Token-Typ, der die Definition eines Konstruktors einleitet & construct \\
THIS & Token-Typ, der für die Referenz auf das aktuelle Objekt steht & this \\
SUPER & Token-Typ, der die Referenzierung auf ein Oberklassenobjekt einleitet & super \\
HASDYNAMICTYPE & Token-Typ, für den dynamischen Typ-Test & hasdynamictype \\
LENGTH & Token-Typ, für den Länge-Operator bei Arrays & length \\
\\
\multicolumn{3}{c}{\textbf{Ein- und Ausgabe}} \\
OUT & Token-Typ, der eine Ausgabe einleitet & out \\
IN & Token-Typ, der eine Eingabe einleitet & in \\
\\
\multicolumn{3}{c}{\textbf{Operatoren}} \\
QMARK & Token-Typ für den bedingten Ausdruck & ? \\
NOT & Token-Typ für logische Negation & ! \\
MUL & Token-Typ für Multiplikation & * \\
DIVORSLASH & Token-Typ für Division und Repräsentation eines Slashes & / \\
MOD & Token-Typ für Rest-Berechnung & \% \\
PLUS & Token-Typ für Addition & + \\
MINUS & Token-Typ für Subtraktion & - \\
HOCH & Token-Typ für Hoch-Rechnung & $^{\wedge}$ \\
SHL & Token-Typ für Links-Shift & << \\
SHR & Token-Typ für Rechts-Shift & >> \\
LT & Token-Typ für Kleiner-Vergleich & < \\
LE & Token-Typ für Kleiner-Gleich-Vergleich & <= \\
GT & Token-Typ für Größer-Vergleich & > \\
GE & Token-Typ für Größer-Gleich-Vergleich & >= \\
EQ & Token-Typ für Gleich-Vergleich & == \\
NE & Token-Typ für Ungleich-Vergleich & != \\
BITAND & Token-Typ für bitweise Und-Verknüpfung & \& \\
BITOR & Token-Typ für bitweise Oder-Verknüpfung & | \\
AND & Token-Typ für logische Und-Verknüpfung & \&\& \\
OR & Token-Typ für logische Oder-Verknüpfung & || \\
XOR & Token-Typ für logische Exlusiv-Oder-Verknüpfung & $^{\wedge\wedge}$ \\
INCREMENT & Token-Typ für Inkrementierung um 1 & ++ \\
DECREMENT & Token-Typ für Dekrementierung um 1 & -- \\
\\
\multicolumn{3}{c}{\textbf{Modifiers}} \\
PUBLIC & Token-Typ für Public-Attribut & public \\
PRIVATE & Token-Typ für Private-Attribut & private \\
PROTECTED & Token-Typ für Protected-Attribut & protected \\
CONST & Token-Typ für Const-Attribut & const \\
STATIC & Token-Typ für Static-Attribut & static \\
OVERRIDE & Token-Typ für Override-Attribut & override \\
\\
\multicolumn{3}{c}{\textbf{Kontrollfluss}} \\
THROW & Token-Typ, der die jeweilige Methode als Fehlermeldung ausgebende Methode markiert & throw \\
THROWS & Token-Typ, der das Werfen der Fehlermeldung einleitet & throws \\
BREAK & Token-Typ, der die Unterbrechung der innersten Schleife einleitet & break \\
TRY & Token-Typ, der einen try-Block einleitet (\textit{Exception handling}) & try \\
CATCH & Token-Typ, der die catch-Klausel einleitet (\textit{Exception handling}) & catch \\
FINALLY & Token-Typ, der die finally-Klausel einleitet (\textit{Exception handling}) & finally \\
\\
\multicolumn{3}{c}{\textbf{Token-Typ ohne Kategorie}} \\
NONE & Token-Typ, der anzeigt, dass das vorliegende Programm keine Main-Klasse enthält & none \\
IMPORT & Token-Typ, der den import-Ausdruck einleitet (Einfügen von externem Quellcode) & import \\
AS & Token-Typ, der in Verbindung mit MainClass auftaucht & as \\
BACKSLASH & Token-Typ, der das $\backslash$-Zeichen repräsentiert & $\backslash$ \\
CAST & Token-Typ, der signalisiert, dass nun eine Typumwandlung folgt & cast \\
\end{longtable}
\normalsize
\pagebreak
\section{Funktionsweise des SO-Lexers}
Bei der Erzeugung eines Lexer-Objektes wird dem Lexer der zu untersuchende Quelltext als Parameter mitgegeben. Bereits im Konstruktoraufruf wird die Methode \texttt{read()} aufgerufen. Diese untersucht nun rekursiv den Quelltext, bis der Lexer am Ende angelangt ist. Dabei geht er wie folgt vor:
\begin{itemize}
 \item Trifft er auf einen Kommentar (eingeleitet durch \texttt{\#} oder \texttt{/+}) so wird dieser übersprungen.
 \item Trifft er auf eine Zahl, so werden solange Zeichen eingelesen, bis keine Zahl mehr auftaucht. Ist das nächste Zeichen dann ein Punkt, so werden weiterhin alle folgenden Ziffern eingelsen. Es handelt sich dann um eine Fließkommazahl.
 \item Trifft der Lexer auf einen Buchstaben, dann werden alle folgenden Buchstaben, Ziffern und Unterstriche eingelesen. Ist diese Zeichenkette dann die Stringrepräsentation eines Keywords (z.B.: \texttt{while}, \texttt{for}, \dots) so wird das jeweilige Token an den Token Strom angehängt, andernfalls handelt es sich um einen Bezeichner.
 \item Stößt der Lexer auf ein Sonderzeichen, so wird festgestellt ob sich um einen Operatoren o.Ä. handelt (z.B.: \texttt{++}, \texttt{/=}, \dots ). Anschließend wird das jeweilige Token erstellt und an die Token-Liste angehängt, oder wenn es sich nicht um ein reserviertes Sonderzeichen handelt, wird ein \textit{ERR}-Token erstellt.
\end{itemize}
Genauere Informationen zur konkreten Implementierung finden Sie im \href{http://sobjects.funpic.de/doc/}{Java-Doc}.
\chapter{Parser}
\index{Parser}
\section{Definition Parser}
Ein Parser (engl.: \textit{to parse - analysieren}) ist ein Computerprogramm oder eine Routine, die für die Zerlegung und Umwandlung eines linearen Eingabe-Stroms in eine brauchbare Form zuständig ist. In dieser Phase der syntaxtischen Analyse, wird der Eingabe-Strom anhand einer sogenannten Grammatik transformiert.
\section{Parserbau - Eigenbau oder Generator}
Am Anfang des Parsers steht eben diese Frage, ob man sich Parser-Generatoren bedient, die mit der Eingabe (der Grammatik) einen Parser erzeugen. Ich habe mich gegen solche Generatoren entschieden, da dies ein Lernprojekt ist. Somit würde es für das Verständnis über die Funktionen eines Parsers wenig nutzen, wenn man sich lediglich in der Grammatik und der Bedienung eines Generators auskennt, aber von der Implementierung in eine konkrete Programmiersprache nichts.
\section{Grobe Funktionsweise}
Im Wesentlichen besteht die Klasse \textit{Parser} nur aus Methoden, die auf unterschiedliche Teile der Grammatik spezialisiert sind. Diese rufen sich untereinander rekursiv solange auf, bis das Token vom Typ \textit{EOF} (end of file) erscheint. Im Allgemeinen sind lediglich folgende Felder und Methoden von enormer Bedeutung:
\begin{itemize}
 \item \textit{currentInstanceNumber, currentLocalVar, currentMethodVar, currentTypeVar} sind Zähler, die zur eindeutigen Identifizierungen von Variablen, Methoden, Klassen und klasseninternen Feldern dienen. 
 \item \textit{pointer} ist eine Variable vom Typ \textit{Integer} und dient als Zeiger auf die aktuelle Stelle im Token-Strom an der sich der Parser im Moment befindet.
 \item \textit{boolean peek(TokenType ... tokenTypes)} ist eine Methode, die beim Aufruf angibt, ob das nächste Token von gegebenem Typ ist. Dies ist wertvoll bei den Fallunterscheidungen in den parse-Methoden.
 \item \textit{Token accept(TokenType ... tokenTypes)} ist eine Methode, die beim Aufruf das aktuelle Token zurückgibt, wenn es von gegebenem Typ ist. Ist dies nicht der Fall wird eine \textit{ParserException} geworfen. Der \textit{pointer} wird um eins erhöht.
 \item \textit{void returnMethod()} ist eine Methode, die den Zähler um eins erniedrigt. Dies ist nützlich wenn man tiefe Verzweigungen hat, aber den eigentlichen parse-Vorgang der Übersichtlichkeit halber in eine neue Methode auslagern möchte.
\end{itemize}
Genaueres zu den Methoden und Feldern sowie Informationen zu den parse-Unter-routinen findet man im Java-Doc.
\section{Grammatik - Herzstück des Compilers}
Wie bereits in der Überschrift erwähnt ist, zumindest für mich, das Herzstück des Compilers, da sie die komplette Syntax festlegt. Das zweite Herzstück ist natürlich die Klassen im Paket \textit{special\_tree}, die die Analyse-Phasen implementieren. Nun möchte ich hier die Grammatik der SO-Programmiersprache auflisten. Doch zuvor noch eine Definition.
\subsection{Definition: Grammatik}
\index{Grammatik}
Eine Grammatik, auch formale Grammatik, ist ein mathematisches Modell, das der Beschreibung und Erzeugung formaler 
Sprachen dient. Die formale Grammatik legt fest, ob ein Wort Element der Sprache ist, sowie ob der vorliegende (Quell-) 
Text den Produktionsregeln der Grammatik genügt. Diese Überprüfung und die anschließende Erzeugung des \textit{Abstract 
Syntax Tree} sind wesentlich für den Compiler.\\[0.3cm]
Zunächst aber einige Konventionen, die man kennen sollte, um die Grammatik lesen zu können.
\begin{lstlisting}[caption=Definition eines Non-Terminal,frame=tlbr]
 <Name des zu definierenden Non-Terminals> ::= <Definition>
\end{lstlisting}
Der ::= Operator definiert einen Art Alias, ein sogenanntes Non-Terminal, welches eine bestimmte Sequenz von Terminalen
und Non-Terminalen repräsentiert und verwendet wird um die formale Grammatik übersichtlich zu halten.
\begin{lstlisting}[caption=Alternativen,frame=tlbr]
 <name> ::= <Alternative1> | <Alternative2>
\end{lstlisting}
Der | Operator gibt verschiedene Möglichkeiten einer Definition für das Non-Terminal \textit{name}. Welche Alternative
gewählt wird hängt von der zu prüfenden Programm-Sequenz ab. Generell kann genau eine Alternative pro Auftreten von
\textit{name} eintreten.
\begin{lstlisting}[caption=Test,frame=tlbr]
 <name> ::= <Teil1> ( <Alternative1> | <Alternative2> ) <Teil2>
\end{lstlisting}
Diese Konstruktion ist ähnlich wie in Listing 4.2. Der einzige Unterschied ist, dass der Anfang, bzw. das Ende der
Programmsequenz die \textit{name} genügt, \textit{Teil1}, bzw. \textit{Teil2} genügen muss. Der Zwischenteil muss
genau einer Alternative genügen.
\begin{lstlisting}[caption=Test,frame=tlbr]
 <name> ::= <Definition> [ <Optionaler Anteil> ] 
\end{lstlisting}
Die [\dots ] - Klammern definieren einen optionalen Anteil. Trifft der Parser auf eine Programsequenz, die \textit{Definition}
genügt, so testet er ob der nachfolgende Teil dem optionalen Anteil ébenfalls genügt. Wenn ja, wird beides zusammen zu
einem Knoten eines \textit{Abstract Syntax Tree} zusammengefasst, anderenfalls nur der erste Teil.\\[0.3cm]
Diese Konstrukte können beliebig verschachtelt auftreten. Aus diesen Basis-Konstrukten lässt sich eine vollwertige
formale Grammatik gewinnen.\\[0.3cm]
Sollten Namen wie \textit{Terminale}, \textit{Non-Terminale} oder \textit{Abstract Syntax Tree} unbekannt sein, empfehle
ich Ihnen Kapitel \ref{chapterTree} zu lesen.
\subsection{Die SO - Grammatik}
\index{Grammatik}
\begin{tabularx}{\textwidth}{rcp{10cm}}
 \textit{compilationunit} & ::= & /* \textit{empty} */ \\
& | & \textit{mainclassdecl} [ \textit{importdeclarations} ] \textit{typedeclarations} \\
\textit{mainclassdecl} & ::= & \texttt{MainClass : } ( \textit{qualifiedname} | \texttt{none} ) \texttt{;} \\
\textit{importdeclarations} & ::= & \textit{importdeclaration} [ \textit{importdeclarations} ] \\
\textit{typedeclarations} & ::= & \textit{typedeclaration} [ \textit{typedeclarations} ] \\
\textit{importdeclaration} & ::= & \texttt{import} \textit{filename} \texttt{as} \textit{identifier} \texttt{;} \\
\textit{identifier} & ::= & \texttt{a} | \dots | \texttt{z} | \texttt{A} | \dots | \texttt{Z} ( \texttt{\_} [ \textit{identifier} ] | \textit{identifier} | \newline \textit{num} [ \textit{identifier} ] ) \\
\textit{num} & ::= & \texttt{0} | \dots | \texttt{9} [ \textit{num} ] \\
\textit{filename} & ::= & \textit{identifier} [ \textit{filename} ] \\
& | & \texttt{:} [ \textit{filename} ] \\
& | & \texttt{/} [ \textit{filename} ] \\
& | & \texttt{$\backslash$} [ \textit{filename} ] \\
& | & \texttt{.} [ \textit{filename} ] \\
\textit{name} & ::= & \textit{qualifiedname} \\
& | & \textit{identifier} \\
\textit{qualifiedname} & ::= & \textit{name} \texttt{.} \textit{identifier} \\
\textit{typedeclaration} & ::= & \textit{classdeclaration} \\
& | & \textit{interfacedeclaration} \\
\textit{interfacedeclaration} & ::= & \texttt{interface} \textit{identifier} [ \textit{extendsexpr} ] \textit{interfacebody} \\
\textit{extendsexpr} & ::= & \texttt{extends} \textit{reftypelist} \\
\textit{reftypelist} & ::= & \textit{referencetype} [ \texttt{,} \textit{reftypelist} ] \\
\textit{classdeclaration} & ::= & \texttt{class} \textit{identifier} [ \textit{extendsexpr} ] [ \textit{implementsexpr} ] \newline \textit{classbody} \\
\textit{implementsexpr} & ::= & \texttt{implements} \textit{reftypelist} \\
\textit{modifiers} & ::= & \textit{modifier} [ \textit{modifiers} ] \\
\textit{modifier} & ::= & \texttt{public} \\
& | & \texttt{private} \\
& | & \texttt{protected} \\
& | & \texttt{const} \\
& | & \texttt{static} \\
& | & \texttt{override} \\
\textit{interfacebody} & ::= & \texttt{$\{$} [ \textit{interfacememberdeclarations} ] \texttt{$\}$} \\
\textit{interfacememberdeclarations} & ::= & \textit{fielddeclaration} [ \textit{interfacememberdeclarations} ] \\
& | & \textit{methodheader} \texttt{;} [ \textit{interfacememberdeclarations} ] \\
\textit{classbody} & ::= & \texttt{$\{$} [ \textit{staticinitializer} ] [ \textit{constructors} ] \newline [ \textit{classmemberdeclarations} ] \texttt{$\}$} \\
\textit{classmemberdeclarations} & ::= & \textit{fielddeclaration} [ \textit{classmemberdeclarations} ] \\
& | & \textit{methoddeclaration} [ \textit{classmemberdeclarations} ] \\
\textit{methoddeclaration} & ::= & \textit{methodheader statement} \\
\textit{fielddeclaration} & ::= & \textit{variabledeclaration} \texttt{;} \\
& | & \textit{vardeclandassignment} \texttt{;} \\
\end{tabularx}

\begin{tabularx}{\textwidth}{rcp{10cm}}
\textit{vardeclandassignment} & ::= & \textit{variabledeclaration} \texttt{=} \textit{expression} \\
\textit{identifierlist} & ::= & \textit{identifier} [ \texttt{,} \textit{identifierlist} ] \\
\textit{type} & ::= & \textit{primitivetype} \\
 & | & \textit{referencetype} \\
\textit{primitivetype} & ::= & \texttt{boolean} \\
& | & \texttt{int} \\
& | & \texttt{long} \\
& | & \texttt{float} \\
& | & \texttt{double} \\
& | & \texttt{char} \\
& | & \texttt{string} \\
\textit{referencetype} & ::= & \textit{arraytype} \\
& | & \textit{identifier} \\
\textit{arraytype} & ::= & \textit{type} \texttt{[ ]} \\
\textit{methodheader} & ::= & [ \textit{modifiers} ] ( \textit{type} | \texttt{void} ) \textit{identifier} \texttt{(} [ \textit{paramlist} ] \texttt{)} \newline [ \textit{throwsdeclaration} ] \\
\textit{staticinitializer} & ::= & \texttt{static} \textit{block} \\
\textit{constructors} & ::= & \textit{constructor} [ \textit{constructors} ] \\
\textit{constructor} & ::= & \textit{constructorheader constructorbody} \\
\textit{constructorheader} & ::= & [ \textit{modifiers} ] \texttt{construct (} [ \textit{paramlist} ] \texttt{)} \newline [ \textit{throwsdeclaration} ] \\
\textit{constructorbody} & ::= & \texttt{\{} [ \textit{constructorinvocation} ] [ \textit{blockstatements} ] \texttt{\}} \\
\textit{constructorinvocation} & ::= & \texttt{this (} [ \textit{exprlist} ] \texttt{)} \\
& | & \texttt{super (} \textit{identifier} \texttt{) (} [ \textit{exprlist} ] \texttt{)} \\
\textit{exprlist} & ::= & \textit{expression} [ \texttt{,} \textit{exprlist} ] \\
\textit{throwsdeclaration} & ::= & \texttt{throws} \textit{reftypelist} \\
\textit{paramlist} & ::= & \textit{param} [ \texttt{,} \textit{paramlist} ] \\
\textit{param} & ::= & \textit{type identifier} \\
\textit{variabledeclaration} & ::= & [ \textit{modifiers} ] \textit{type identifier} \\
\textit{block} & ::= & \texttt{\{} [ \textit{blockstatements} ] \texttt{\}} \\
\textit{blockstatements} & ::= & \textit{blockstatement} [ \textit{blockstatements} ] \\
\textit{blockstatement} & ::= & \textit{localvardeclandassignment} \texttt{;} \\
& | & \textit{statement} \\
\textit{localvardeclandassignment} & ::= & \textit{variabledeclaration} \hspace{1cm} \textit{/* without modifiers */} \\
& | & \textit{vardeclandassignment} \hspace{0.45cm} \textit{/* without modifiers */}
\end{tabularx}

\begin{tabularx}{\textwidth}{rcp{10cm}}
\textit{statement} & ::= & \textit{ifstatement} \\
& | & \textit{whilestatement} \\
& | & \textit{forstatement} \\
& | & \textit{block} \\
& | & \textit{emptystatement} \\
& | & \textit{expressionstatement} \\
& | & \textit{switchstatement} \\
& | & \textit{breakstatement} \\
& | & \textit{throwstatement} \\
& | & \textit{trystatement} \\
& | & \textit{returnstatement} \\
& | & \textit{outputstatement} \\
\textit{outputstatement} & ::= & \texttt{out (} \textit{expression} \texttt{) ;} \\
\textit{ifstatement} & ::= & \texttt{if (} \textit{expression} \texttt{)} \textit{statement} [ \texttt{else} \textit{statement} ] \\
\textit{whilestatement} & ::= & \texttt{while (} \textit{expression} \texttt{)} \textit{statement} \\
\textit{forstatement} & ::= & \texttt{for (} [ \textit{forinit} ] \texttt{;} \textit{expression} \texttt{;} [ \textit{forupdate} ] \texttt{)} \newline \textit{statement} \\
\textit{emptystatement} & ::= & \texttt{;} \\
\textit{expressionstatement} & ::= & \textit{assignment} \texttt{;} \\
& | & \textit{preincrementexpression} \texttt{;} \\
& | & \textit{predecrementexpression} \texttt{;} \\
& | & \textit{postincrementexpression} \texttt{;} \\
& | & \textit{postdecrementexpression} \texttt{;} \\
& | & \textit{methodinvocation} \texttt{;} \\
\textit{switchstatement} & ::= & \texttt{switch (} \textit{expression} \texttt{)} \textit{switchblock} \\
\textit{breakstatement} & ::= & \texttt{break ;} \\
\textit{returnstatement} & ::= & \texttt{return} [ \textit{expression} ] \texttt{;} \\
\textit{throwstatement} & ::= & \texttt{throw} \textit{expression} \texttt{;} \\
\textit{trystatement} & ::= & \texttt{try} \textit{block catch} [ \textit{finally} ] \texttt{;} \\
\textit{forinit} & ::= & \textit{statementexpressionlist} \\
\textit{forupdate} & ::= & \textit{statementexpressionlist} \\
\textit{assignment} & ::= & \textit{lefthandside assignmentoperator expression} \\
\textit{preincrementexpression} & ::= & \texttt{++} \textit{unaryexpression} \\
\textit{predecrementexpression} & ::= & \texttt{-{-}} \textit{unaryexpression} \\
\textit{postincrementexpression} & ::= & \textit{primary} \texttt{++} \hspace{0.5cm} \textit{/* only restricted primary */} \\
\textit{postdecrementexpression} & ::= & \textit{primary} \texttt{-{-}} \hspace{0.5cm} \textit{/* only restricted primary */} \\
\textit{methodinvocation} & ::= & [ \textit{primary} \texttt{.} ] \textit{identifier} \texttt{(} \textit{argumentlist} \texttt{)} \\
\textit{switchblock} & ::= & \texttt{\{ \}} \\
& | & \texttt{\{} \textit{switchblockstatementgroups} \texttt{\}} \\
\textit{switchblockstatementgroups} & ::= & \textit{switchblockstatementgroup} \newline [ \textit{switchblockstatementgroups} ] \\
\textit{switchblockstatementgroup} & ::= & \textit{switchlabels blockstatements} \\
\textit{switchlabels} & ::= & \textit{switchlabel} [ \textit{switchlabels} ] \\
\textit{switchlabel} & ::= & \texttt{case} \textit{expression} \texttt{:} \\
& | & \texttt{default :}
\end{tabularx}

\begin{tabularx}{\textwidth}{rcp{10cm}}
\textit{catch} & ::= & \texttt{catch (} \textit{param} \texttt{)} \textit{block} \\
\textit{finally} & ::= & \texttt{finally} \textit{block} \\
\textit{statementexpressionlist} & ::= & \textit{expressionstatement} [ \texttt{,} \textit{statementexpressionlist} ] \\
\textit{lefthandside} & ::= & \textit{name} \\
& | & \textit{fieldaccess} \\
& | & \textit{arrayaccess} \\
\textit{assignmentoperator} & ::= & \texttt{/=} \\
& | & \texttt{*=} \\
& | & \texttt{\%=} \\
& | & \texttt{+=} \\
& | & \texttt{-=} \\
& | & \texttt{<{<}=} \\
& | & \texttt{>{>}=} \\
& | & \texttt{\&=} \\
& | & \texttt{|=} \\
& | & \texttt{$^{\wedge}$=} \\
\textit{fieldaccess} & ::= & \textit{primary} \texttt{.} \textit{identifier} \\
\textit{arrayaccess} & ::= & ( \textit{name} | \textit{primarynonewarray} ) \texttt{[} \textit{expression} \texttt{]} \\
\textit{unaryexpression} & ::= & \texttt{+} \textit{unaryexpression} \\
& | & \texttt{-} \textit{unaryexpression} \\
& | & \texttt{!} \textit{unaryexpression} \\
& | & \textit{primary} \\
\textit{castexpression} & ::= & \texttt{cast (} \textit{type} \texttt{)} \textit{unaryexpression} \\
\textit{expression} & ::= & \textit{conditionalexpression} \\
\textit{conditionalexpression} & ::= & \textit{orexpression} [ \texttt{?} \textit{expression} \texttt{:} \textit{conditionalexpression} ] \\
\textit{orexpression} & ::= & [ \textit{orexpression} \texttt{||} ] \textit{andexpression} \\
\textit{andexpression} & ::= & [ \textit{andexpression} \texttt{\&\&} ] \textit{bitorexpression} \\
\textit{bitorexpression} & ::= & [ \textit{bitorexpression} \texttt{|} ] \textit{xorexpression} \\
\textit{xorexpression} & ::= & [ \textit{xorexpression} \texttt{$^{\wedge\wedge}$} ] \textit{bitandexpression} \\
\textit{bitandexpression} & ::= & [ \textit{bitandexpression} \texttt{\&} ] \textit{equalityexpression} \\
\textit{equalityexpression} & ::= & [ \textit{equalityexpression} ( \texttt{==} | \texttt{!=} ) ] \textit{relationalexpression} \\
\textit{relationalexpression} & ::= & [ \textit{relationalexpression} ( \texttt{<} | \texttt{>} | \texttt{<=} | \texttt{>=} ) ] \textit{shiftexpression} \\
\textit{shiftexpression} & ::= & [ \textit{shiftexpression} ( \texttt{<{<}} | \texttt{>{>}} ) ] \textit{additiveexpression} \\
\textit{additiveexpression} & ::= & [ \textit{additiveexpression} ( \texttt{+} | \texttt{-} ) ] \textit{multiplicativeexpression} \\
\textit{multiplicativeexpression} & ::= & [ \textit{multiplicativeexpression} ( \texttt{*} | \texttt{/} | \texttt{\%} ) ] \textit{powexpression} \\
\textit{powexpression} & ::= & [ \textit{powexpression} \texttt{$^{\wedge}$} ] \textit{unaryexpression} \\
\textit{primary} & ::= & \textit{primarynonewarray} \\
& | & \textit{arraycreationexpression} \\
\textit{arraycreationexpression} & ::= & \texttt{new} \textit{type dimexprs} \\
\textit{dimexprs} & ::= & \textit{dimexpr} [ \textit{dimexprs} ] \\
\textit{dimexpr} & ::= & \texttt{[} \textit{expression} \texttt{]} \\
\end{tabularx}

\begin{tabularx}{\textwidth}{rcp{10cm}}
\textit{primarynonewarray} & ::= & \textit{literal} \\
& | & \texttt{this} \\
& | & \texttt{super (} \textit{referencetype} \texttt{)} \\
& | & \texttt{(} \textit{expression} \texttt{)} \\
& | & \textit{classinstancecreationexpression} \\
& | & \textit{fieldaccess} \\
& | & \textit{methodinvocation} \\
& | & \textit{arrayaccess} \\
& | & \textit{lengthexpr} \\
& | & \textit{castexpression} \\
& | & \textit{preincrementexpression} \\
& | & \textit{predecrementexpression} \\
& | & \textit{postincrementexpression} \\
& | & \textit{postdecrementexpression} \\
& | & \textit{primary} \texttt{hasdynamictype} \textit{type} \\
& | & \textit{inputexpression} \\
& | & \textit{identifier} \\
\textit{lengthexpr} & ::= & \textit{primary} \texttt{.length} \\
\textit{inputexpression} & ::= & \texttt{in (} \textit{type} \texttt{) ;} \\
\textit{classinstancecreationexpression} & ::= & \texttt{new} \textit{referencetype} \texttt{)} \textit{argumentlist} \texttt{)} \\
\textit{literal} & ::= & \textit{num} \\
& | & \textit{num} ( \texttt{l} | \texttt{L} ) \\
& | & \textit{num} \texttt{.} \textit{num} ( \texttt{f} | \texttt{F} ) \\
& | & \textit{num} \texttt{.} \textit{num} \\
& | & \texttt{false} \\
& | & \texttt{true} \\
& | & \texttt{a} | \dots | \texttt{Z} | \texttt{\_} | \texttt{0} | \dots \hspace{0.5cm} \textit{/* ascii-characters */} \\
& | & \texttt{null} \\
& | & \texttt{\textgravedbl} \textit{string} \texttt{\textacutedbl} \\
\textit{string} & ::= & \textit{/* any ascii-character string */}
\end{tabularx}
\\[0.5cm]
Dies ist die vorläufige Grammatik-Spezifikation der SO-Programmiersprache. An einigen Stellen kann es sein, dass sie mehrdeutig oder auch unvollständig ist. Auch sind an einigen Stellen noch Einschränkungen zu beachten. Diese sind nicht immer vermerkt. Für die konkrete Implementierung des Parsers sind sie jedoch zu beachten. Dies sind normalerweise Einschränkungen, wie man sie aus anderen Programmiersprachen kennt. Sie wurden nicht berücksichtigt, um die Grammatik noch relativ einfach zu halten. Die Grammatik wird ständig aktualisiert.
\pagebreak
\section{Parser als UML-Diagramm}
Eine weitere gängige Art, Klassen und Pakete zu spezifizieren ist UML (\textit{Unified Modeling Language}). Genaueres dazu unter \url{http://de.wikipedia.org/wiki/UML}. Ich möchte nun die wichtigsten Bestandteile des Parsers durch ein UML-Diagramm verdeutlichen.
\begin{center}
 \includegraphics[width=10cm]{uml_parser.eps}
\end{center}
Im UML-Diagramm sind alle Felder und Methoden aufgeführt, außer die Hilfsmethoden der Methode \textit{parse(boolean isImport)}. Für genaueres, schauen Sie im Java-Doc.
\chapter{TreeFactory}
\index{TreeFactory}
Das Interface \textit{TreeFactory} ist eine Schnittstelle, die die Erzeugung aller Bäume übernimmt. Dabei folgt \textit{TreeFactory} dem Entwurfsmuster \textit{abstrakte Fabrik}, das ich nun im Folgenden erläutern möchte. Dabei wird ein UML-Diagramm helfen. \textit{MyTreeFactory} implementiert \textit{TreeFactory} und kann als \textit{konkrete Fabrik} angesehen werden.
\section{Abstrakte Fabrik}
\index{Fabrik}
\index{Abstrakte Fabrik}
Die \textit{Abstrakte Fabrik} (engl. \textit{abstract factory}) ist ein Entwurfsmuster (engl. \textit{implementation pattern}) aus dem Bereich der Softwareentwicklung und gehört zu der Kategorie der Erzeugungsmuster (engl.\textit{creational patterns}). Es definiert eine Schnittstelle zur Erzeugung einer Familie von Objekten, wobei die konkreten Klassen der zu instanzierenden Objekte dabei nicht näher festgelegt werden. Im Konkreten sieht das folgendermaßern aus:
\begin{center}
 \includegraphics[width=10cm]{TreeFactory.eps}
\end{center}
Dabei hat der Parser Zugriff auf die \textit{konkrete Fabrik} um mit ihr (unabhängig von der konkreten Implementierung von MyTreeFactory) alle benötigten Bäume zu erzeugen. Der Parser hat ebenfalls Zugriff auf alle Bäume, deren dynamischer Typ aus dem Paket \textit{special\_tree} stammt, ohne deren konkrete Implemntierung zu kennen. Alle Operationen müssen in \textit{Tree} spezifiziert werden, da kein Zugriff auf interne Methoden erfolgen kann. Das bietet folgende Vorteile:
\begin{itemize}
 \item Das System kann unabhängig von der Art der Erzeugung seiner Produkte arbeiten.
 \item Eine Gruppe von Produkten kann erzeugt und gemeinsam genutzt werden.
 \item Die Produkte werden mit ihren Schnittstellen bereitgestellt, ohne dass die Implementierung bekannt sein muss.
\end{itemize}
\section{MyTreeFactory}
Die \textit{konkrete Fabrik} MyTreeFactory implementiert die Schnittstelle TreeFactory und beinhaltet die Implementierungen der \textit{make\dots}(\textit{\dots }) - Methoden aus TreeFactory. \\[0.2 cm]
Der Name der Methoden ist streng aufgebaut. Das \textit{make} wird gefolgt von einer Baumbeschreibung, die den erzeugten Baum näher benennt. Dieser Baumname ist auch fester Bestandteil der Klassennamen der \textit{special trees}. Die Methoden rufen im Wesentlichen den Konstruktor des zugehörigen \textit{Abstract Syntax Tree} auf und leiten ihre Argumente weiter.\\[0.2 cm]
Im Folgenden nun eine Liste aller \textit{make\dots}(\textit{\dots }) - Methoden. Für Kurzbeschreibungen lesen Sie im Kapitel
\ref{specialTree} nach. 
\texttt{
\begin{itemize}
 \item makeArrayAccess(Token, Tree, List<Tree>)
 \item makeAssign(Token, Tree, Tree)
 \item makeBinOp(Token, Tree, Tree)
 \item makeBlock(Tree ...)
 \item makeBreakStatement(Token)
 \item makeCatch(Token, Tree, Tree)
 \item makeClassDecl(Token, int, Type[], Type[], Tree)
 \item makeClassInstanceCreation(Token, Type, List<Tree>)
 \item makeCond(Token, Tree, Tree, Tree)
 \item makeConstructorDeclaration(List<Modifiers>, Token,\\ List<Type>, Tree, Tree, int)
 \item makeConstructorInvokation(Token, Tree)
 \item makeDecl(Token, Type, int)
 \item makeDynamicTypeTest(Token, Tree, Type)
 \item makeEmptyStatement(Token)
 \item makeExplicitTypeCast(Token, Type, Tree)
 \item makeFieldAccess(Token, Tree)
 \item makeForLoop(Token, Tree, Tree, Tree, Tree)
 \item makeGlobalDecl(List<Modifiers>, Token, Type, int)
 \item makeIf(Token, Tree, Tree)
 \item makeIfElse(Token, Tree, Tree, Tree)
 \item makeImport(Token[], Map<String, Tree>, Tree ...)
 \item makeInput(Token, Type)
 \item makeInterfaceDecl(Token, int, Type[], Tree)
 \item makeLengthExpr(Token, Token, Tree)
 \item makeList(Tree ...)
 \item makeLiteral(Token)
 \item makeLocalArrayAccess(Token, List<Tree>)
 \item makeLocalVarAccess(Token)
 \item makeMethodDeclaration(List<Modifiers>, Token, Type,\\ Tree, List<Type>, Tree, int)
 \item makeMethodHeader(List<Modifiers>, Token, Type, Tree, List<Type>)
 \item makeMethodInvocation(Token, Tree, Tree[])
 \item makeMethodInvocationStaticWithinOwnClass(Token, Tree[])
 \item makeNewArray(Token, Type, List<Tree>)
 \item makeOutput(Token, Tree)
 \item makePostIncDec(Token, Tree)
 \item makePreIncDec(Token, Tree)
 \item makeProgram(Token[], Map<String, Tree>, Tree ...)
 \item makeReturn(Token, Tree)
 \item makeStaticInitializer(Token, Tree)
 \item makeSuperAccess(Token, Type)
 \item makeSwitch(Token, Tree, Tree)
 \item makeSwitchGroup(Token, Tree, Tree)
 \item makeThisAccess(Token)
 \item makeThrowException(Token, Tree)
 \item makeTry(Token, Tree, Tree, Tree)
 \item makeUnOp(Token, Tree)
 \item makeWhile(Token, Tree, Tree)
\end{itemize} }
\chapter{Tree}
\index{Tree}
\label{chapterTree}
\section*{Kurze Einführung mathematischer Grundbegriffe}
Kennen Sie grundlegenden mathematische Symbole oder haben Sie mathematisches Vorwissen, dann können Sie diesen Abschnitt
getrost hinter sich lassen. Für alle anderen gebe ich hier kurz Definition für die hier verwendeten Symbole $\subseteq$,
$\times$ und $\in$, sowie für den Begriff Menge.
\begin{Def}
 Mengen (Mengenlehre) ist ein grundlegender Bestandteil der Mathematik. Eine Menge in unserem Sinne ist eine Ansammlung
von Elementen, die sich meist ähneln, z.B.: Zahlen oder hier konkret Terminal-Symbole (siehe unten).
\end{Def}
\begin{Def}
 Das Symbol $\in$ tritt immer in folgender Anordnung auf: \newline $<Element> \in <Menge>$.\newline Hierbei testet der Operator, ob eine
gegebenes Element in einer gegebenen Menge enthalten ist. Das Ergebnis ist entweder \textit{wahr} oder \textit{falsch}.
\end{Def}
Beispiel: $1 \in \{1, 2, 3\} \Rightarrow wahr$ oder $4 \in \{1, 2, 3\} \Rightarrow falsch$
\begin{Def}
 Der Operator $\subseteq$ ist auf zwei Mengen definiert: $<Menge> \subseteq <Menge>$ Er testet ob die linke Menge eine
Teilmenge der rechten Menge ist. Eine Teilmenge von einer gegebenen Menge ist eine Menge, die eine Auswahl oder alle
Elemente der Menge enthält. Das Ergebnis ist wieder entweder \textit{wahr} oder \textit{falsch}.
\end{Def}
Beispiel: $\{1, 2\}  \subseteq \{1, 2, 3\} \Rightarrow wahr$ oder $\{4\} \subseteq \{1, 2, 3\} \Rightarrow falsch$
\begin{Def}
 Das letzte Symbol $\times$ bildet aus zwei Mengen das sogenannte kartesische Produkt, welches wiederum eine Menge ist.
In dieser Menge befinden sich alle möglichen Paare von Elementen aus der einen Mengen und der anderen Menge.
\end{Def}
Beispiel: $\{1, 2\}\times \{a, b\} \Rightarrow \{(1, a),(1, b),(2, a),(2, b)\}$
\\[0.3cm]
Dies sollte als mathematisches Grundverständnis reichen, um die nun folgenden, gegebenermaßen komplexen und sehr formalen
Teil zu verstehen, die allerdings unerlässlich sind, um die Struktur des Compilers zu verstehen.
\pagebreak
\section{Bäume -  Eine Datenstruktur}
\index{Baum}
Allgemeine Bäume definiert man am Besten über eine rekursive Definition. Der Duden Informatik \cite{DINFO} sagt dazu:
\begin{quote}
 Anschaulich baut man Bäume durch folgende rekursive Vorschrift auf:
 \begin{itemize}
  \item[(1)] Ein einzelner \textbf{Knoten} ist ein Baum.
  \item[(2)] Wenn $B_1,B_2,\dots,B_n$ für $n\geq 1$ Bäume sind, dann ist auch die Struktur gemäß der Abbildung
 ~\ref{fig:defbild} ein Baum. 
 \end{itemize}
\end{quote}
\begin{figure}[h!]
 \begin{center}
 \begin{pspicture}(0,0)(4,2)
 \rput(2,1){
    \pstree[nodesepB=3pt]{\Tdot}{\TR{$B_1$} \TR{$B_2$} \TR{\dots} \TR{$B_n$}}
  }
\end{pspicture}
\end{center}
\caption{Definition Baum}
\label{fig:defbild}
\end{figure}
Die Bäume $B_1,B_2,\dots,B_n$ heißen nun \textbf{Teilbäume} (engl.: subtree). Der oberste Knoten heißt \textbf{Wurzel} 
(engl.: root). Der einfachste Baum besteht dann wie gesagt aus einem Knoten und ist in Abbildung ~\ref{fig:mintree} zu sehen.
Aus ihm lassen sich alle anderen Bäume bauen.
\begin{figure}[h!]
 \begin{center}
 \begin{pspicture}(0,0)(0,0)
 \rput(0,-1){
    \pstree{\Tdot}{}
  }
\end{pspicture}
\end{center}
\caption{Einfachster Baum}
\label{fig:mintree}
\end{figure}
\\[0.3cm]
Eine zweite Definition bedient sich der Graphentheorie. Zunächst zur Definition eines gerichteten Graphen. Diesmal liefert
uns \textit{Programmierung - Eine Einführung in die Informatik} \cite{GS2007} eine gute Definition:
\begin{quote}
 Ein \textbf{gerichteter Graph} $G$ ist ein Paar $(V, E)$, das aus einer Menge $V$ und einer Menge $E \subseteq V \times V$
besteht. Die Elemente von $V$ werden als die \textbf{Knoten} und die Elemente von $E$ als die Kanten des Graphen bezeichnet.
Wir sagen, dass eine Kante $(v,w)$ von $v$ nach $w$ führt.
\end{quote}
Weiterhin heißt ein Knoten \textbf{Wurzel}, wenn er keinen Vorgänger hat, also keine Kante, die zu ihm hinführt. Ein \textbf{Zyklus}
ist ein Weg von einem Knoten zum selben über einen anderen. Ein Graph heißt \textbf{azyklisch} wenn er keinen Zyklus hat.
\pagebreak
\begin{figure}[h!]
 \begin{center}
 \begin{pspicture}(0,0)(3,3)
 \cnodeput(1,1){A}{A}
 \cnodeput(2,2){B}{B}
 \cnodeput(3,1){C}{C}
 \ncline{->}{A}{B}
 \ncline{->}{B}{C}
 \ncline{->}{C}{A}
\end{pspicture}
\end{center}
\caption{Graph mit Zyklus}
\end{figure}
\newline
Wie definiert man nun aus diesen Eigenschaften die Definition eines Baumes?
\begin{Def}
\label{gerGraph}
 Einen \textbf{gerichteten Graphen} $G(V,E)$ mit folgenden Eigenschaften nennt man \textbf{Baum}:
\begin{itemize}
\item $G$ hat genau eine Wurzel.
\item $G$ ist azyklisch.
\end{itemize}
\end{Def}
Unsere Datenstruktur im Compiler kann selbstverständlich kein sogenannter reiner Baum sein, da eben alle reinen Bäume aus den
gleichen Elementen bestehen. Bei einem Syntax-Baum, dem sogenannten \textbf{Abstract Syntax Tree} gibt es mehrere
unterschiedliche Knotentypen und noch weitere Knotenattribute. Dazu aber mehr im nächsten Kapitel\ \ref{AST}.

\section{Abstract Syntax Tree - Angepasste Datenstruktur}
\index{AST}
\index{Abstract Syntax Tree}
\label{AST}
Der \textit{Abstract Syntax Tree} bezeichnet eine Art der Zwischendarstellung von Quelltexten. Viele moderne
Compiler verwenden intern diese Darstellung, da sie sich sehr gut dazu eignet, leicht und rekursiv, alle Analysephasen zu
durchlaufen. Der Quelltext wird mithilfe des Lexers zerlegt und mit dem Parser anhand von sogenannten \textit{Produktionsregeln}
(oder auch Ableitungsregeln) in eine solche Zwischendarstellung transformiert. Dabei finden sich alle wichtigen Informationen
des Quelltexts im \textbf{AST} wieder. \\[0.3cm] Aber zunächst zu diesen Produktionsregeln. Diese bestehen aus einer Reihe
von Symbolen, den sogenannten Terminal- und Non-Terminal-Symbolen. Diese sind eine Definition an dieser Stelle wert, da sie
sehr leicht im Abstract Syntax Tree wiederzufinden sind.
\begin{Def}
 Ein \textbf{Terminalsymbol} bezeichnet eine nicht weiter teilbare Einheit innerhalb einer Produktionsregel. Dies ist in 
unserer formalen Grammatik beispielsweise ein Token, z.B.: ein Bezeichner oder eine Ganzzahl-Konstante. \newpage
Ein \textbf{Non-Terminal-Symbol} bezeichnet eine komplexere Struktur, die aus weiteren Non-Terminal-Symbolen, sowie auch Terminal-
Symbolen besteht. Sie sind somit \textit{induktiv} definierbar.
\begin{itemize}
\item Das kleinste Non-Terminal-Symbol repräsentiert ein Terminal-Symbol, oder eine Folge von Terminal-Symbolen.
\item Jedes größere Non-Terminal-Symbol lässt sich auf weitere Non-Terminal-Symbole und schließlich nur
auf Terminale zurückführen.
\end{itemize}
Auch kann sich das aktuell definierende Non-Terminal selbst rekursiv aufrufen, weswegen es zu einer längeren Liste
aus Terminalen kommen kann, welche die selbe Sequenz mehrfach enthält.
\end{Def}
Diese recht abstrakte Definition möchte ich jetzt an einem Beispiel verdeutlichen.
\begin{lstlisting}[caption=Test,frame=tlbr]
 book ::= cover content
 cover ::= AUTOR YEAR
 content ::= page [ content ]
 page ::= LETTER [ page ]
\end{lstlisting}
\label{listingGram}
Nun zur Erklärung.\textit{book} ist ein Non-Terminal bestehend aus den Non-Terminalen \textit{cover} und 
\textit{content}.\textit{cover} seinerseits besteht aus den beiden Terminalen \textbf{AUTOR} und \textbf{YEAR}. Man könnte diese noch in Buchstaben
und Zahlen weiterzerlegen. Man sieht also, dass es Sache der Festlegung ist, was Terminal ist und was nicht. \textit{content}
und \textit{page} haben ähnlichen Aufbau. \textit{page} besteht konkret aus einem Terminal und eines optionalen rekursiven
Aufrufs von sich selbst. Dadurch entsteht im konkreten \textgravedbl Quelltext\textacutedbl \ eine beliebig lange Liste
von \textbf{LETTER}-Terminalen für \textit{page}.
\\[0,5cm]
Nun zum eigentlich \textit{Abstract Syntax Tree}. Wie bereits im vorherigen Kapitel gesagt, besitzt ein baum Knoten und Kanten.
\newline Zunächst zu den Kanten. Die Kanten sind unbeschriftet und beinhalten im Wesentlichen keine Informationen. Allerdings tragen
sie den großen Anteil der Struktur des programms mit. Ein AST ist eben auch genau deshalb so einfach. Struktur teile aus dem Quelltext
können nun entfernt werden, da der AST durch seinen Aufbau bereits alles aussagt. Solche Struktur-Zeichen sind z.B.:
\texttt{\{ ( ; , . <! !> [ ] ) \}}. \\[0,3cm]
Die Knoten sind wieder etwas komplexer. Ein Knoten besteht eigentlich aus Non-Terminalen. Also ein Baum zu dem obigen Listing
sieht so aus:\pagebreak
\begin{figure}[h!]
 \begin{center}
 \begin{pspicture}(0,-1)(4,4)
 \rput(2,1){
    \pstree[nodesepB=3pt]{\TR{book}}{\TR{cover} \pstree[nodesepB=3pt]{\TR{content}}{ 
	\TR{page} \TR{...}}}
  }
\end{pspicture}
\end{center}
\caption{Buch - Baum}
\label{buchBaum}
\end{figure}
\newline
Die Terminale sind nun wichtig, um die einzelnen Knoten genauer zu beschreiben. Sind zum Beispiel alle \textit{page}-Knoten
aus Sicht der Non-Terminale gleich, so ist aber noch lange nicht ihr Inhalt gleich. Ein Buch besteht aus mehreren Seiten,
repräsentiert durch viele \textit{page}-Knoten. Aber stellen Sie sich ein Buch vor, bei dem auf jeder Seite das gleiche steht \dots\ 
Hier kommen die Terminalsymbole ins Spiel. Diese spezifizieren sozusagen den eigentlichen \textgravedbl Inhalt\textacutedbl .
\\[0.3cm]
Man sagt auch, dass die Terminale die \textbf{Attribute} der jeweiligen Knoten sind. In unserem Fall ist nun eine Liste von
Terminalen des Typs \textbf{LETTER} das Attribut eines \textit{page}-Knoten. Wie dies konkret modelliert und in einer 
Programmiersprache umgesetzt wird, sehen Sie in den nächsten Kapiteln \ref{tree} und \ref{mytree} . \\[0.3cm]
Zum Abschluss gibt es jetzt noch die formale Definition eines \textit{Abstract Syntax Tree}. 
\begin{Def}
Ein \textbf{Abstract Syntax Tree} (kurz: {\normalfont AST}) ist gemäß Definition \ref{gerGraph} ein \textbf{gerichteter}, 
\textbf{azyklischer} und \textbf{gewurzelter} (Graph hat genau eine Wurzel) Graph $G(V,E)$ mit $E \subseteq V \times V$.
\textbf{$E$} ist die Menge aller Kanten, wobei eine Kante durch ein Paar von Knoten beschrieben wird. \textbf{$V$} ist die 
Menge aller Knoten. \\[0.3cm]
Die Menge aller Knoten $V$ ist ein \textbf{Paar} $(nt, [ t_1,t_2,\dots ,t_n ] )$, wobei $nt \in NT$ (Menge aller \textbf{Non-Terminale}) und
$t_1,t_2,\dots t_n \in T$ (Menge aller \textbf{Terminale}) ist. Die Mengen $NT$ und $T$ sind \textbf{eindeutig} durch eine formale \textbf{Grammatik}
bestimmt.
\end{Def}
\underline{Bemerkung:}
\begin{quote}
 Ein \textit{AST} kann gemäß der obigen Definitione Knoten mit beliebigen Kombinationen von Terminalen und Non-Terminalen
beinhalten. In der Praxis ist dies nicht so. So kann beispielsweise ein Knoten der eine Multiplikation repräsentiert kein
Terminal \textbf{PUBLIC} (ein Zugriffsbeschränker) enthalten. Dies sicherzustellen, obliegt den Analysephasen. Diese Aufteilung
ist vergleichbar mit der syntaktischen Analyse der Quelltexts mit Lexer (vergleiche AST aufbauen) und Parser (vergleiche
Korrektheit sicherstellen).
\end{quote}
Der erste Teil der Definition dürfte kein Verständnisproblem bereiten. Für die Mengen $NT$ und $T$ gebe ich im folgenden noch ein Beispiel
um diesen Abschnitt zu verdeutlichen. Hierbei beziehe ich mich auf die formale Grammatik aus Listing 6.1 aus Kapitel
\ref{listingGram}. Als letztes möchte ich dann die Abbildung \ref{buchBaum} verfeinern.\\[0.3cm]
Schauen wir uns wieder das Grammatik-Listing an. Non-Terminale können weiter zu Terminalen zerlegt werden, müssen also definiert
werden. Dies geschieht auf der linken Seite. Außerdem werden Non-Terminale nach Konvention klein geschrieben. Somit ist es nun
kein Problem die Menge $NT$ zu bilden. Es gilt also: 
\begin{equation*}
 NT = \{ book, cover, content, page \}
\end{equation*}
Terminale andereseits tauchen nur 
auf der rechten Seite der Vereinbarungen auf und werden nicht auf der linken Seite definiert. Des Weiteren werden Terminale
per Konvention mit Großbuchstaben geschrieben. Also gilt für die Menge $T$:
\begin{equation*}
 T = \{ AUTOR, YEAR, LETTER \}
\end{equation*}
Zum Schluss nun noch der \textgravedbl verfeinerte\textacutedbl\ AST, der lediglich neue, eindeutige Knoten hat gemäß der
Definition eines \textit{Abstract Syntax Tree}.
\begin{figure}[h!]
 \begin{center}
 \begin{pspicture}(0,-1)(4,4)
 \rput(2,1){
    \pstree[nodesepB=3pt]{\TR{(book, )}}{\TR{(cover, [Sebastian Hahn, 2009])} \pstree[nodesepB=3pt]{\TR{(content, )}}{ 
	\TR{(page, [S, O, -, C, O, M, P, I, L, E, R]) } \TR{(page, [\dots])} \TR{\dots}}}
  }
\end{pspicture}
\end{center}
\caption{Buch - AST}
\end{figure}
\pagebreak
\section{Tree}
\index{Tree}
\label{tree}
\section{MyTree}
\index{MyTree}
\label{mytree}
\chapter{Symboltabellen für Variablen, Felder, Klassen, Methoden}
\index{Scope}
\index{Symboltabellen}
\chapter{Analysephasen}
\index{Analysephasen}
\section{Namensanaylse}
\index{Namensanalyse}
\section{Typüberprüfung}
\index{Typüberprüfung}
\section{Optimierung}
\index{Optimierung}
\section{Codegenerierung}
\index{Codegenerierung}
\chapter{Codegenerierung - Tool}
\section{Die Klasse IRBuilder}
\index{IRBuilder}
\section{Die Klasse Code}
\index{Code}
\chapter{Special Trees}
\index{Special Tree}
\index{special\_tree}
\label{specialTree}
\chapter{Compiler}
\index{Compiler}
\chapter{Beispiele}
\chapter{Zukunftsaussichten}
\part{Anhang}
\begin{appendix}
 \chapter{Programmieren in SO}
\end{appendix}
%\backmatter
\begin{thebibliography}{999}
 \bibitem{GS2007} Prof. Dr. Gert Smolka, Eine Einführung in die Informatik mit Standard ML,\newline Oldenbourg Wissenschaftsverlag, 2008
 \bibitem{WIKI} \url{http://de.wikipedia.org}
 \bibitem{ÜOPS} Bernhard Bauer, Riitta Höllerer, Übersetzung objektorientierter Programmiersprachen, Springer-Lehrbuch, 1998
 \bibitem{LLVMLR} Chris Lattner, Vikram Adve, LLVM Language Reference Manual, \newline \url{http://llvm.org/docs/LangRef.html}
 \bibitem{LLVM} \url{http://llvm.org}
 \bibitem{COMP} Alfred V. Aho, Monica S. Lam, Ravi Sethi, Jeffrey D. Ullman, Compiler, \newline Pearson Studium, 2008
 \bibitem{DINFO} Duden Informatik, Duden Verlag, 4. Auflage, 2003, ISBN 3-411-04484-5
\end{thebibliography}

\printindex
\end{document}
